from typing import *


class BinaryIndexedTree():

    def __init__(self, ceil: int) -> None:
        self.ceil = ceil + 10
        self.array = [0] * self.ceil

    def initArray(self, nums: List[int]):
        for i, v in enumerate(nums):
            self.add(i, v)

    def lowbit(self, index: int) -> int:
        return index & -index

    def add(self, index: int, value: int) -> None:
        # index 增加 value
        index += 1
        while index < self.ceil:
            self.array[index] += value
            index += self.lowbit(index)

    def query(self, index: int) -> int:
        # 查询[0,index]的和
        index += 1
        ret = 0
        while index > 0:
            ret += self.array[index]
            index -= self.lowbit(index)
        return ret

    def valueAt(self, index: int) -> int:
        # 查询index处值
        return self.query(index) - self.query(index - 1)

    def update(self, index: int, value: int) -> None:
        # 更新index数值为value
        val = self.valueAt(index)
        diff = value - val
        self.add(index, diff)


class NumArray:

    def __init__(self, nums: List[int]):
        self.bid = BinaryIndexedTree(len(nums))
        self.bid.initArray(nums)

    def update(self, index: int, val: int) -> None:
        self.bid.update(index, val)

    def sumRange(self, left: int, right: int) -> int:
        return self.bid.query(right) - self.bid.query(left - 1)


na = NumArray([1, 3, 5])
print(na.sumRange(0, 2), na.update(1, 2), na.sumRange(0, 2))
